public class LeetCode {
    public String longestPalindrome(String s) {
        // char[] arr = s.toCharArray();
        // int sz = s.length();
        // boolean[][] dp = new boolean[sz][sz];
        // String ans = "";
        // //需要注意遍历顺序
        // //由于当前状态室友左下角的状态转移的,需要先求出这个状态
        // for(int i = sz - 1; i >= 0; i--){
        //     for(int j = 0; j < sz; j++){
        //         if(arr[i] == arr[j]){
        //             if((j - i <= 1)||(j - i > 1 && dp[i+1][j-1])){
        //                 dp[i][j] = true;
        //                 if(j - i + 1 > ans.length()){
        //                     ans = s.substring(i, j+1);
        //                 }
        //             }else{
        //                 dp[i][j] = false;
        //             }
        //         }else{
        //             dp[i][j] = false;
        //         }
        //     }
        // }
        // return ans;

        char[] arr = s.toCharArray();
        int n = s.length();
        String ans = "";
        for(int i = 0; i < n; i++){
            int l = i - 1, r = i + 1;
            while(l >= 0 && r < n && arr[l] == arr[r]){
                l--;
                r++;
            }
            l++;
            r--;
            if(r-l+1 > ans.length()){
                ans = s.substring(l, r+1);
            }

            if(i-1 >= 0 && arr[i-1] == arr[i]){
                l = i - 1 - 1;
                r = i + 1;
                while(l >= 0 && r < n && arr[l] == arr[r]){
                    l--;
                    r++;
                }
                l++;
                r--;
                if(r-l+1 > ans.length()){
                    ans = s.substring(l, r+1);
                }
            }
        }
        return ans;
    }
}
